Traditional social networking services store social graph data in data shards either randomly or according to a sequence in which corresponding user accounts are created. Each data shard is a partition of data in a database for the social graph. The data shards are stored in separate database server instances to spread data access load. A traditional social networking service also includes a mapping data structure to map user identifications (IDs) of the social networking users to the data shards which store the social graph data of the users. When the social networking service receives a request for accessing data associated with multiple related users, the social networking service determines the storage locations based on the mapping data structure and retrieves data from various locations of the data shards. The cache for the data shards is ineffective, because the data associated with the related users are typically not stored together.